package cn.orange.ch08_backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * LC216.组合总和III
 */
public class LC216 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> trace = new LinkedList<>();
        backtracking(1, k, n, trace, ans);
        return ans;
    }

    private void backtracking(int start, int k, int n, LinkedList<Integer> trace, List<List<Integer>> ans) {
        if (k == 0 & n == 0) {
            ans.add(new ArrayList<>(trace));
            return;
        }
        for (int i = start; i <= 9; i++) {
            if (9 - i + 1 < k) continue;
            if (i > n) continue;
            trace.add(i);
            backtracking(i + 1, k - 1, n - i, trace, ans);
            trace.removeLast();
        }
    }

    public static void main(String[] args) {
        LC216 alg = new LC216();
        System.out.println(alg.combinationSum3(3, 7));
        System.out.println(alg.combinationSum3(3, 9));
        System.out.println(alg.combinationSum3(4, 1));
    }
}
